home *** CD-ROM | disk | FTP | other *** search
/ Mission 3 / Mission 3.zip / Mission 3.iso / texte / qed / src / memory.c < prev    next >
C/C++ Source or Header  |  1998-10-19  |  14KB  |  680 lines
  1. #include "global.h"
  2. #include "qed.h"
  3. #include "memory.h"
  4.  
  5. #undef MAGIC
  6. #define MAGIC            0xFED1
  7. #define MAX_ANZ        261 /* 132 */    /* 67 */    
  8. #define BLOCK_SIZE    (MAX_ANZ*4)
  9. #define BLOCKANZ        50 /* 100 */  /* 200 */            /* Für einen malloc */
  10. #define MEMSIZE        ((long)BLOCK_SIZE*BLOCKANZ)    /* für einen malloc */
  11.  
  12. #define MEM_SIZE(x)    (((x)+2+3)&(~3))                        /* 2 Bytes drauf für den Kopf */
  13. #define MEM_ADD(x,d)    (BLOCK*)((char*)(x)+(d))
  14. #define MEM_SUB(x,d)    (BLOCK*)((char*)(x)-(d))
  15.  
  16. typedef union tblock
  17. {
  18.     struct
  19.     {
  20.         unsigned int magic;                /* 2 Bytes */
  21.         unsigned int size;                    /* 2 Bytes */
  22.         union tblock *next;        /* 4 Bytes */
  23.         union tblock *prev;        /* 4 Bytes => 12 Bytes */
  24.     } FREI;
  25.     struct
  26.     {
  27.         unsigned int size;        /* 2 Bytes */
  28.     } USED;
  29. } BLOCK;
  30.  
  31. static bool        mem_need_BS,                    /* BS hat keinen Speicher mehr */
  32.                     mem_need_TQ;                    /* TQ hat keinen Speicher mehr */
  33. static BLOCK*    free_list[MAX_ANZ+1+1];        /* ein Dummy am Ende */
  34. static void*    block_list;
  35.  
  36.  
  37. static bool new_block(void)
  38. {
  39.     BLOCK *adr, *adr2, *pre;
  40.     long  *ptr;
  41.     long    anz, i;
  42.  
  43.     anz = (long) Malloc(-1L);
  44.     if (anz >= 4 + MEMSIZE + 4)
  45.     {
  46.         ptr = (long *) Malloc(4 + MEMSIZE + 4);
  47.         anz -= 4 + MEMSIZE + 4;
  48.     }
  49.     else
  50.         ptr = NULL;
  51.     if (anz < MEMSIZE + 20000L)
  52.         mem_need_BS = TRUE;
  53.     if (ptr == NULL)
  54.     {
  55.         if (anz >= 4 + BLOCK_SIZE + 4)
  56.         {
  57.             i = anz = (anz - 8)/(BLOCK_SIZE);
  58.             anz = 4 + (anz * BLOCK_SIZE) + 4;
  59.             ptr = (long *) Malloc(anz);
  60.         }
  61.         else
  62.         {
  63.             mem_need_TQ = TRUE;
  64.             mem_need_BS = TRUE;
  65.             return FALSE;
  66.         }
  67.         mem_need_TQ = TRUE;
  68.     }
  69.     else
  70.     {
  71.         i = BLOCKANZ;
  72.         mem_need_TQ = FALSE;
  73.     }
  74.  
  75.     *(void**)ptr = block_list;            /* In Liste einhängen */
  76.     block_list = ptr;
  77.  
  78.     adr = MEM_ADD(ptr,4);
  79.     free_list[MAX_ANZ] = adr;
  80.     pre = NULL;
  81.     while ((--i)>0)
  82.     {
  83.         adr2 = MEM_ADD(adr,BLOCK_SIZE);
  84.         *(long*)&adr->FREI.magic = (long)(MAGIC<<16)+BLOCK_SIZE;
  85.                                             /*    adr->FREI.magic = MAGIC;        */
  86.                                             /*    adr->FREI.size = BLOCK_SIZE;    */
  87.         adr->FREI.next = adr2;
  88.         adr->FREI.prev = pre;
  89.         pre = adr;
  90.         adr = adr2;
  91.     }
  92.     adr2 = MEM_ADD(adr,BLOCK_SIZE);
  93.     *(long*)&adr->FREI.magic = (long)(MAGIC<<16)+BLOCK_SIZE;
  94.                                         /*    adr->FREI.magic = MAGIC;        */
  95.                                         /*    adr->FREI.size = BLOCK_SIZE;    */
  96.     adr->FREI.next = NULL;
  97.     adr->FREI.prev = pre;
  98.  
  99.     *(long*)adr2 = 0L;            /* damit bei FREE da kein MAGIC steht */
  100.  
  101.     return TRUE;
  102. }
  103.  
  104. static void *MALLOC(unsigned int size)
  105. {
  106.     BLOCK *adr, **feld;
  107.  
  108.     size = MEM_SIZE(size);
  109.     if (size > BLOCK_SIZE)
  110.     {
  111.         debug("\aMalloc: size= %d (> %d)\n", size, BLOCK_SIZE);
  112.         note(1, 0, FATALMEM);
  113.         return NULL;
  114.     }
  115.  
  116.     feld = (BLOCK**)((char*)free_list+size);
  117.     if (*feld == NULL)                                            /* kein passender */
  118.     {
  119.         if (size+16<=BLOCK_SIZE)                                /* größeren Block suchen und teilen */
  120.         {
  121.             BLOCK *adr2;
  122.             int    i;
  123.  
  124.             i = size+16; feld += 4;                                /* 16 Bytes kleinster Block zum Abspalten */
  125.             while (TRUE)                                            /* größeren Block suchen */
  126.             {
  127.                 if (*feld++!=NULL) 
  128.                     break; i+=4;
  129.             }
  130.             feld--;
  131.             if (i==(BLOCK_SIZE+4))                                /* kein Block vorhanden */
  132.             {
  133.                 if (!new_block())
  134.                     return NULL;
  135.                 feld--; i-=4;
  136.             }
  137.             adr = *feld;                                            /* Zeiger auf Block */
  138.             *feld = adr->FREI.next;                                /* Aushängen */
  139.             if (*feld!=NULL) (*feld)->FREI.prev = NULL;
  140.             adr->USED.size = size;
  141.  
  142.             /* Rest in die free_list einhängen */
  143.             adr2 = MEM_ADD(adr,size);                                /* Zeiger auf Restblock */
  144.             (char*)feld -= size;
  145.             i -= size;                                                /* Restgröße */
  146.             adr2->FREI.magic = MAGIC;                            /* Einhängen */
  147.             adr2->FREI.size = i;
  148.             adr2->FREI.next = *feld;
  149.             adr2->FREI.prev = NULL;
  150.             if (*feld!=NULL) (*feld)->FREI.prev = adr2;
  151.             *feld = adr2;
  152.         }
  153.         else                                                            /* größten Block nehmen */
  154.         {
  155.             feld = (BLOCK**)(&free_list[MAX_ANZ]);
  156.             if (*feld==NULL)                                        /* kein Block vorhanden */
  157.                 if (!new_block())
  158.                     return NULL;
  159.             adr = *feld;                                            /* Zeiger auf Block */
  160.             *feld = adr->FREI.next;                                /* Aushängen */
  161.             if (*feld!=NULL) (*feld)->FREI.prev = NULL;
  162.             adr->USED.size = BLOCK_SIZE;
  163.         }
  164.     }
  165.     else                                                                /* passend vorhanden */
  166.     {
  167.         adr = *feld;                                                /* Zeiger auf Block */
  168.         *feld = adr->FREI.next;                                    /* Aushängen */
  169.         if (*feld!=NULL) (*feld)->FREI.prev = NULL;
  170.         adr->USED.size = size;
  171.     }
  172.     if (free_list[MAX_ANZ]==NULL)
  173.         mem_need_TQ = TRUE;
  174.     return(MEM_ADD(adr,2));
  175. }
  176.  
  177. static void FREE(void *adr)
  178. {
  179.     int    size1, size2;
  180.     BLOCK *adr1, *adr2, **feld;
  181.  
  182.     adr1 = MEM_SUB(adr,2);                                        /* adr1 auf ersten Block */
  183.     size1 = adr1->USED.size;
  184.     adr2 = MEM_ADD(adr1,size1);                                /* adr2 auf Nachfolger */
  185.     size2 = adr2->FREI.size;
  186.     if (adr2->FREI.magic==MAGIC && (size1+size2<=BLOCK_SIZE))
  187.     /* freier Block dahinter => Zusammenfügen */
  188.     {
  189.         BLOCK    *pre;
  190.  
  191.         pre = adr2->FREI.prev;                                    /* Aushängen */
  192.         if (pre==NULL)                                                /* erster in der Liste */
  193.             *(BLOCK**)((char*)free_list+size2) = adr2->FREI.next;
  194.         else
  195.             pre->FREI.next = adr2->FREI.next;
  196.         if (adr2->FREI.next!=NULL)                                /* es gibt Nachfolger */
  197.             adr2->FREI.next->FREI.prev = pre;
  198.         size1 += size2;
  199.     }
  200.     feld = (BLOCK**)((char*)free_list+size1);                /* Einhängen */
  201.     adr1->FREI.magic = MAGIC;
  202.     adr1->FREI.size = size1;
  203.     adr1->FREI.next = *feld;
  204.     adr1->FREI.prev = NULL;
  205.     if (*feld!=NULL) (*feld)->FREI.prev = adr1;
  206.     *feld = adr1;
  207.  
  208.     if (size1 == BLOCK_SIZE)
  209.         mem_need_TQ = FALSE;
  210. }
  211.  
  212. /* =========================================================== */
  213.  
  214. void INSERT(ZEILEP *a, int pos, int delta, char *str)
  215. {
  216.     char    *ptr;
  217.     
  218.     ptr = REALLOC(a,pos,delta);
  219.     memcpy(ptr, str, delta);
  220. }
  221.  
  222. /* =========================================================== */
  223.  
  224. char *REALLOC(ZEILEP *a, int pos, int delta)
  225. {
  226.     ZEILEP    col;
  227.     int        new_len;
  228.     BLOCK     *adr;
  229.  
  230.     col = *a;
  231.     if (delta == 0) 
  232.         return(TEXT(col) + pos);
  233.  
  234.     new_len = col->len+delta;
  235.     if (new_len < 0 || new_len > MAX_LINE_LEN)
  236.     {
  237.         debug("\aREALLOC: new_len= %d (> %d)\n", new_len, MAX_LINE_LEN);
  238.         note(1, 0, FATALMEM);
  239.         return NULL;
  240.     }
  241.     adr = MEM_SUB(col,2);
  242.     if (MEM_SIZE((unsigned int)sizeof(ZEILE)+new_len+1) != adr->USED.size)
  243.     {
  244.         ZEILEP    new;
  245.  
  246.         new = MALLOC( (int) sizeof(ZEILE) + new_len + 1);
  247.         if (new == NULL)
  248.             return NULL;
  249.         memcpy(new, col, sizeof(ZEILE)+pos);
  250.         if (delta<0)
  251.         {
  252.             new->len = new_len;
  253.             memcpy(TEXT(new) + pos, TEXT(col) + pos - delta, new_len - pos + 1);
  254.         }
  255.         else
  256.         {
  257.             memcpy(TEXT(new) + pos + delta, TEXT(col) + pos, col->len - pos + 1);
  258.             new->len = new_len;
  259.         }
  260.         new->is_longest = col->is_longest;
  261.         FREE(col);
  262.         new->vorg->nachf = new;
  263.         new->nachf->vorg = new;
  264.         *a = new;
  265.         new->exp_len = -1;
  266.         return(TEXT(new)+pos);
  267.     }
  268.     else    /* Der Platzt in der Zeile reicht */
  269.     {
  270.         if (delta < 0)
  271.         {
  272.             col->len = new_len;
  273.             memcpy(TEXT(col) + pos, TEXT(col) + pos - delta, new_len - pos + 1);
  274.         }
  275.         else
  276.         {
  277.             memmove(TEXT(col) + pos + delta, TEXT(col) + pos, col->len - pos + 1);
  278.             col->len = new_len;
  279.         }
  280.         col->exp_len = -1;
  281.         return(TEXT(col)+pos);
  282.     }
  283. }
  284.  
  285. ZEILEP new_col(char *str, int l)
  286. {
  287.     ZEILEP     a;
  288.     
  289.     a = (ZEILEP)MALLOC( (int) sizeof(ZEILE)+l+1);
  290.     if (a != NULL)
  291.     {
  292.         a->info = 0;
  293.         a->len = l;
  294.         a->exp_len = -1;
  295.         a->is_longest = FALSE;
  296.         memcpy(TEXT(a), str, l);
  297.         TEXT(a)[l] = EOS;
  298.     }
  299.     return(a);
  300. }
  301.  
  302. void free_col(ZEILEP col)
  303. {
  304.     FREE(col);
  305. }
  306.  
  307. /* Zeile nach WO einfügen      */
  308. ZEILEP col_insert(ZEILEP wo, ZEILEP was)
  309. {
  310.     ZEILEP help;
  311.  
  312.     help = wo->nachf;
  313.     help->vorg = was;
  314.     was->nachf = help;
  315.     was->vorg = wo;
  316.     wo->nachf = was;
  317.     return was;
  318. }
  319.  
  320. /* Zeile am Ende anhängen */
  321. void col_append(RINGP t, ZEILEP was)
  322. {
  323.     ZEILEP help;
  324.  
  325.     help = LAST(t);
  326.     was->vorg = help;
  327.     was->nachf = help->nachf;
  328.     help->nachf = was;
  329.     t->tail.vorg = was;
  330.     t->lines++;
  331. }
  332.  
  333. void col_delete(RINGP t, ZEILEP was)
  334. {
  335.     was->vorg->nachf = was->nachf;
  336.     was->nachf->vorg = was->vorg;
  337.     FREE(was);
  338.     t->lines--;
  339. }
  340.  
  341. void col_concate(ZEILEP *wo)
  342. {
  343.     ZEILEP        help, col;
  344.     bool    absatz;
  345.  
  346.     col = *wo;
  347.     help = col->nachf;
  348.     if (col->len)
  349.     {
  350.         absatz = help->info&ABSATZ;
  351.         INSERT(&col, col->len, help->len, TEXT(help));
  352.         help->nachf->vorg = col;
  353.         col->nachf = help->nachf;
  354.         FREE(help);
  355.         if (absatz)
  356.             col->info |= ABSATZ;
  357.         else
  358.             col->info &= ~ABSATZ;
  359.         *wo = col;
  360.     }
  361.     else
  362.     {
  363.         col->vorg->nachf = help;
  364.         help->vorg = col->vorg;
  365.         FREE(col);
  366.         *wo = help;
  367.     }
  368. }
  369.  
  370. void col_split(ZEILEP *col,int pos)
  371. {
  372.     ZEILEP    new,help;
  373.     int        anz;
  374.     bool        absatz, overlen;
  375.  
  376.     help = *col;
  377.     absatz = IS_ABSATZ(help);
  378.     help->info &= ~ABSATZ;
  379.     overlen = IS_OVERLEN(help);
  380.     help->info &= ~OVERLEN;
  381.     if (pos==0)
  382.     {
  383.         new = new_col("",0);
  384.         col_insert(help->vorg,new);
  385.         *col = new;
  386.     }
  387.     else if (pos<help->len)
  388.     {
  389.         anz = help->len-pos;
  390.         new = new_col(TEXT(help)+pos, anz);
  391.         col_insert (help, new);
  392.         REALLOC(&help,pos,-anz);
  393.         *col = help;
  394.     }
  395.     else
  396.     {
  397.         new = new_col("",0);
  398.         col_insert(help,new);
  399.     }
  400.     if (absatz) 
  401.         (*col)->nachf->info |= ABSATZ;
  402.     else 
  403.         (*col)->nachf->info &= ~ABSATZ;
  404.     if (overlen) 
  405.         (*col)->nachf->info |= OVERLEN;
  406. }
  407.  
  408. /* 
  409.  * Wieviel WhiteSpace-Zeichen stehen am Anfang der Zeile?
  410. */
  411. int col_offset(ZEILEP col)
  412. {
  413.     int    pos;
  414.     char c, *str;
  415.  
  416.     pos = 0;
  417.     str = TEXT(col);
  418.     c = *str++;
  419.     while ((c=='\t' || c==' ') && pos<col->len)
  420.     {
  421.         pos++;
  422.         c = *str++;
  423.     }
  424.     return pos;
  425. }
  426.  
  427. int col_einrucken(ZEILEP *col)
  428. {
  429.     ZEILEP    vor_col;
  430.     int        length;
  431.  
  432.     vor_col = (*col)->vorg;
  433.     if (!IS_HEAD(vor_col))
  434.     {
  435.         length = col_offset(vor_col);
  436.         if ((*col)->len + length > MAX_LINE_LEN)
  437.         {
  438.             inote(1, 0, TOOLONG, MAX_LINE_LEN);
  439.             return 0;
  440.         }
  441.         INSERT(col, 0, length, TEXT(vor_col));
  442.     }
  443.     else
  444.         length = 0;
  445.     return(length);
  446. }
  447.  
  448. ZEILEP get_line(RINGP r, long y)
  449. {
  450.     ZEILEP    lauf;
  451.  
  452.     if (y<0 || y>=r->lines) return NULL;
  453.     if (y<(r->lines>>1))
  454.     {
  455.         lauf = FIRST(r);
  456.         while ((--y)>=0) NEXT(lauf);
  457.     }
  458.     else
  459.     {
  460.         lauf = LAST(r);
  461.         y = r->lines-y;
  462.         while ((--y)>0) VORG(lauf);
  463.     }
  464.     return lauf;
  465. }
  466.  
  467. /*=========================================================================*/
  468.  
  469. /*
  470.  * Ein Text ist als doppelt verkettete Liste implementiert
  471.  * Am Anfang und Ende befindet sich je ein Zeilenkopf der
  472.  * auf NULL zeigt
  473. */
  474.  
  475. void init_textring(RINGP r)
  476. {
  477.     ZEILEP    a;
  478.  
  479.     r->head.info = HEAD;
  480.     r->tail.info = TAIL;
  481.     a = new_col("",0);
  482.     a->nachf = &r->tail;
  483.     a->vorg = &r->head;
  484.     LAST(r) = a;
  485.     r->tail.nachf = NULL;
  486.     FIRST(r) = a;
  487.     r->head.vorg = NULL;
  488.     r->lines = 1;
  489.     r->ending = tos;
  490.     r->max_line_len = MAX_LINE_LEN;
  491. }
  492.  
  493. long textring_bytes(RINGP r)
  494. {
  495.     ZEILEP    lauf, ende;
  496.     long        bytes, overlen = 0;
  497.  
  498.     lauf = FIRST(r);
  499.     ende = LAST(r);
  500.     bytes = lauf->len;
  501.     while(lauf!=ende)
  502.     {
  503.         NEXT(lauf);
  504.         bytes += lauf->len;
  505.         if (IS_OVERLEN(lauf))
  506.             overlen++;
  507.     }
  508.  
  509.     if (r->ending != binmode)
  510.     {
  511.         /* plus Zeilenenden: 1 Zeichen für alle */
  512.         bytes += r->lines - 1 - overlen;
  513.         if (r->ending == tos)
  514.             /* für TOS noch ein Zeichen */
  515.             bytes += r->lines - 1 - overlen;
  516.     }
  517.     return bytes;
  518. }
  519.  
  520. void free_textring(RINGP r)
  521. {
  522.     ZEILEP lauf, frei, ende;
  523.  
  524.     frei = LAST(r);                /* letzte Zeile */
  525.     lauf = frei->vorg;            /* vorletzte Zeile */
  526.     ende = FIRST(r);                /* erste Zeile */
  527.     while (frei!=ende)
  528.     {
  529.         FREE(frei);
  530.         frei = lauf;
  531.         VORG(lauf);
  532.     }
  533.     LAST(r) = frei;
  534.     frei->nachf = &r->tail;
  535.     REALLOC(&frei,0,-(frei->len));
  536.     frei->info = 0;
  537.     r->lines = 1;
  538. }
  539.  
  540. void kill_textring(RINGP r)
  541. {
  542.     free_textring(r);
  543.     FREE(FIRST(r));
  544.     FIRST(r) = NULL;
  545.     LAST(r) = NULL;
  546.     r->lines = 0;
  547. }
  548.  
  549. bool doppeln(RINGP old, RINGP new)
  550. {
  551.     ZEILEP    lauf, neu, a;
  552.     long        lines, anz;
  553.     bool        erg;
  554.  
  555.     erg = TRUE;
  556.     free_textring(new);
  557.     a      = FIRST(new);
  558.     lauf = FIRST(old);
  559.     anz    = old->lines;
  560.  
  561.     INSERT(&a, 0, lauf->len, TEXT(lauf));
  562.     a->info = lauf->info;
  563.     NEXT(lauf);
  564.     NEXT(a);
  565.     lines = 1L;
  566.     while (lines<anz)
  567.     {
  568.         neu = new_col(TEXT(lauf),lauf->len);
  569.         neu->info = lauf->info;                        /* ABSATZ mit kopieren */
  570.         col_insert(a->vorg,neu);
  571.         NEXT(lauf);
  572.         lines++;
  573.         if (!ist_mem_frei())
  574.         {
  575.             erg = FALSE;
  576.             break;
  577.         }
  578.     }
  579.     new->lines = lines;
  580.     new->ending = old->ending;
  581.     new->max_line_len = old->max_line_len;
  582.     return erg;
  583. }
  584.  
  585. bool ist_leer(RINGP r)
  586. {
  587.     return(r->lines==1 && FIRST(r)->len==0);
  588. }
  589.  
  590. /*=========================================================================*/
  591.  
  592. void kill_memory(void)
  593. {
  594.     int            i;
  595.     BLOCK            **ptr;
  596.     void            *help;
  597.     
  598.     for (i = MAX_ANZ + 1, ptr = free_list; (--i) >= 0; )
  599.         *ptr++ = NULL;
  600.  
  601.     while (block_list != NULL)
  602.     {
  603.         help = *(void**)block_list;        /* nächster Block */
  604.         Mfree(block_list);
  605.         block_list = help;
  606.     }
  607.     mem_need_TQ = mem_need_BS = FALSE;
  608. }
  609.  
  610. bool ist_mem_frei(void)
  611. {
  612.     if (mem_need_BS && mem_need_TQ)
  613.     {
  614.         note(1, 0, NOMEMORY);
  615.         return (FALSE);
  616.     }
  617.     else
  618.         return (TRUE);
  619. }
  620.  
  621. void init_memory(void)
  622. {
  623.     int    i;
  624.     BLOCK **ptr;
  625.  
  626.     mem_need_TQ = mem_need_BS = FALSE;
  627.     for (i=MAX_ANZ+1,ptr=free_list; (--i)>=0; )
  628.         *ptr++ = NULL;
  629.     *ptr = (void*)-1L;    /* für schleifenende */
  630.     block_list = NULL;
  631. }
  632.  
  633.  
  634. /* Debug-Funktionen **********************************************************/
  635.  
  636. void dump_freelist(void)
  637. {
  638.     if (debug_level)
  639.     {
  640.         int    i;
  641.         
  642.         debug("dump_freelist...\n");
  643.         for (i = 0; i < MAX_ANZ + 1; i++)
  644.         {
  645.             if ((free_list[i] != NULL) && (free_list[i]->FREI.magic == MAGIC))
  646.             {
  647.                 BLOCK    *p;
  648.                 int    d;
  649.                 
  650.                 p = free_list[i];
  651.                 d = 0;
  652.                 while (p)
  653.                 {
  654.                     d++;
  655.                     p = p->FREI.next;
  656.                 }
  657.                 debug(" [%d].size: %d, Anzahl: %d\n", i, free_list[i]->FREI.size, d);
  658.             }
  659.         }
  660.     }
  661. }
  662.  
  663.  
  664. void dump_ring(RINGP r)
  665. {
  666.     if (debug_level)
  667.     {
  668.         ZEILEP    lauf;
  669.         char        *txt;
  670.             
  671.         lauf = FIRST(r);
  672.         while (!IS_TAIL(lauf))
  673.         {
  674.             txt = TEXT(lauf);
  675.             debug("%s\n", txt);
  676.             NEXT(lauf);
  677.         }
  678.     }
  679. }
  680.